package cn.nawang.ebeim.client.version;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by GanJc on 2016/2/19.
 */
public class Bag {

    static int n  ;  //num of stone
    static int c  ;  //max v

    static int v [] ; //volume
    static int w [] ; //weight

    private static Integer [][] cache ;

    public static int d(int i,int j) {
        if (cache[i][j] != null) {
            return cache[i][j];
        }
        if (i == 0) {
            return 0;
        } else {
            int a = d(i - 1, j);
            int b =0;
            if(j > v[i - 1]){
                b = d(i - 1, j - v[i - 1]) + w[i - 1];
            }
            int d = a > b ? a : b;
            cache[i][j] = d;
            return d;
        }
    }

    //d(3, 10)=max{ d(2, 10), d(2, 7)+12 }
    //d(i, j)=max{ d(i-1, j), d(i-1,j-V[i-1]) + W[i-1] }
    public static void main(String[] args) {
//        test1();
//        test2();
        test3();
    }

    public static void test1(){
        n = 5 ;
        c = 10 ;
        v = new int[]{4,3,5,2,5};
        w = new int[]{9,6,1,4,1};
        cache = new Integer[n+1][c+1];
        int d = d(n, c);
        System.out.println(d);
//        19
//        1 1 0 1 0
    }
    public static void test2(){
        n = 4 ;
        c = 9 ;
        v = new int[]{4,3,4,2};
        w = new int[]{20,6,20,4};
        cache = new Integer[n+1][c+1];
        int d = d(n, c);
        System.out.println(d);
//        40
//        1 0 1 0
    }
    public static void test3(){
        n = 5 ;
        c = 10 ;
        v = new int[]{2,2,6,5,4};
        w = new int[]{6,3,5,4,6};
        cache = new Integer[n+1][c+1];
        int d = d(n, c);
        System.out.println(d);
//        15
//        1 1 0 0 1
    }

}
